package graph;

import linkedGraph.Vertex;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;

public abstract class Graph {
    protected final static int INFINITY = Integer.MAX_VALUE;
    protected final static int BFS = 0;
    protected final static int DFS = 1;

    protected GraphKind kind;
    protected Object[] vexs;  // 顶点集合(顺序存储)
    protected ArrayList<Vertex> vertexList; // 顶点集合(链式存储)
    protected int[][] arcs;   // 邻接关系集合

    protected int vexNum; // 顶点数量
    protected int arcNum; // 边(弧)数量

    protected boolean[] visited; // 是否已被遍历的标志位(长度等于顶点数量)
    protected List<Object> bfsList; // bfs访问序列
    protected List<Object> dfsList; // dfs访问序列
    protected Queue<Integer> queue = new LinkedBlockingDeque<>(); // dfs访问辅助队列

    public Graph() {
    }


    /**
     * 获取顶点数量
     *
     * @return
     */
    public abstract int getVexNum();

    /**
     * 获取边的数量
     *
     * @return
     */
    public abstract int getArcNum();

    /**
     * 按位置取顶点
     *
     * @param v
     * @return
     */
    public abstract Object getVex(int v);

    /**
     * 按值取位置
     *
     * @param vex
     * @return
     */
    public abstract int locateVex(Object vex);

    /**
     * v的第一个邻接点
     *
     * @param v
     * @return
     * @throws Exception
     */
    public abstract int firstAdjVex(int v) throws Exception;

    /**
     * v邻接点w的下一个
     *
     * @param v
     * @param w
     * @return
     */
    public abstract int nextAdjVex(int v, int w);

    public Graph(GraphKind kind, int arcNum, Object[] vexs, int[][] arcs) {
        this.kind = kind;
        this.arcNum = arcNum;
        this.vexNum = vexs.length;
        this.arcs = new int[vexNum][vexNum];
        this.vexs = new Object[vexs.length];   // 初始化顶点数组的值
    }

    /**
     * 深度优先搜索
     *
     * @param startVex 起始顶点的索引
     */
    public void traverseDFS(int startVex) {
        if (startVex < 0 || startVex >= vexNum) {
            System.out.println("不存在第" + startVex + "个顶点");
            return;
        }

        dfsList = new ArrayList<>();
        // 对访问标志位数组进行初始化
        visited = new boolean[this.vexNum];
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }

        dfs(startVex);

        System.out.println("从" + getVex(startVex) + "开始,深度优先遍历序列:" + dfsList.toString());
    }

    /**
     * 深搜核心
     *
     * @param v
     */
    protected abstract void dfs(int v);

    /**
     * 广度优先搜索
     *
     * @param startVex 起始顶点的索引
     */
    public void traverseBFS(int startVex) {
        if (startVex < 0 || startVex >= vexNum) {
            System.out.println("不存在第" + startVex + "个顶点");
            return;
        }

        bfsList = new ArrayList();
        // 对访问标志位数组进行初始化
        visited = new boolean[this.vexNum];
        for (int i = 0; i < vexNum; i++) {
            visited[i] = false;
        }

        // 从第一个顶点出发找它的所有邻接点
        bfs(startVex);

        System.out.println("从" + getVex(startVex) + "开始,广度优先遍历序列:" + bfsList.toString());
    }

    /**
     * 广搜核心
     *
     * @param startVex
     */
    protected abstract void bfs(int startVex);

    /**
     * 显示当前所有顶点
     */
    public abstract void showVexs();

    /**
     * 显示当前图中所有顶点的邻接关系
     */
    public abstract void showArcs();
}
